# class Solution:
#     def combinationSum3(self, k: int, n: int):
#         combinationlist=[]
#         def findcom(k, n, result):
#             if k == 1:
#                 if n>9:
#                     return 0
#                 result.append(n)
#                 combinationlist.append(result)
#             else:
#                 for i in range(result[-1] + 1 if len(result)>0 else 1,int((n + 1) / 2)):
#                     nresult = result[:]
#                     nresult.append(i)
#                     findcom(k - 1, n - i, nresult)
#         findcom(k,n,[])
#         return combinationlist

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result=[]
        def dfs(prev,route,total):
            if total==target:
                result.append(route[:])
            if total>target:
                return 
            for i in candidates:
                if i>=prev:
                    route.append(i)
                    dfs(i,route,total+i)
                    route.pop()
        dfs(candidates[0],[],0)
        return result


'''
执行用时：
88 ms
, 在所有 Python3 提交中击败了
40.06%
的用户
内存消耗：
15 MB
, 在所有 Python3 提交中击败了
25.70%
的用户
'''


solution=Solution()
print(solution.combinationSum3(3,15))

